\begin{frame}
\frametitle{Unambiguous tiling systems}

\begin{define}[unambiguous tiling system \cite{LonatiPradella2011}]
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is unambiguous if and only if 
for any picture $p\in L, L\subseteq\Sigma^{*,*}$ there exists at most one local
picture $q\in LOC(\Theta)$ such that $p = \pi(q)$.
\end{define}

$L \in REC$ is an unmabiguous picture language if and only if it admits an
unambiguous tiling system $(\Sigma, \Gamma, \Theta, \pi)$.

The family of all unambiguous REC picture languages is denoted by UREC.

\end{frame}

\begin{frame}
\frametitle{Column and row unambiguous tiling systems}

\begin{define}[$l2r$-unambiguous tiling system \cite{LonatiPradella2011}]
A tiling system $(\Sigma, \Gamma, \Theta, \pi)$ is $l2r$-unambiguous if for
any local column $col \in \Gamma^{m,1}\cup\{\#\}^{m,1}$, and column picture
$p\in\Sigma^{m,1}$, there exists at most one local column $col'\in \Gamma^{m,1}$
such that $p = \pi(col')$ and \(\left(\{\#\}^{1,2}\varominus(col \varobar col')
\varominus \{\#\}^{1,2}\right) \subseteq \Theta\).
\end{define}

A language is column-unambiguous if it is recognized by a $d$-unambiguous tiling
system for some $d\in\{l2r,r2l\}$ and it is row-unambiguous if it is recognized
by a $d$-unambiguous tiling system for some $d\in\{t2b,b2t\}$.

The family of all column-unambiguous languages is denoted by Col-UREC and
Row-UREC for the family of all row-unambiguous languages.

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Example}
\cite{AnselmoGiammarresiMadonia2007}Let $L_{fr = fc}$ be the language of squares
over a two-letters alphabet $\Sigma = \{a, b\}$ with the first row equal to the
first column. $L_{fr = fc}\in REC$
\begin{example}
$T = (\Sigma, \Gamma, \Theta, \pi)$ is a tiling system, where 
\begin{itemize}
  \item $\Gamma = \{{x}_{y}^{z}$ with $x,y\in\Sigma, z \in \{0, 1, 2\}\}$
  \item $\pi({x}_{y}^{z}) = x$
  \item $0$ descrips positions below the diagonal, $1$ the positions on the
  diagonal and $2$ the position above the diagonal
\end{itemize}
\label{unambiguousTilingSystemExample}
\end{example}
Here below it is given an example of a picture $p \in L_{fr=fc}$ together with
the corresponding local picture $p'$.

\framebreak

\setlength{\tabcolsep}{3pt}
\begin{table}
\begin{tabular}{rl}
$p = $ \begin{tabular}{|c|c|c|c|c|}
\hline
 a & a & b & b & a \\
\hline
 a & b & b & a & a \\
\hline
 b & b & a & a & b \\
\hline
 b & b & a & a & a \\
\hline
 a & a & a & a & b \\
\hline
\end{tabular}
&
$p' = $ \begin{tabular}{|c|c|c|c|c|}
\hline
 ${a}_{a}^{1}$ & ${a}_{a}^{2}$ & ${b}_{b}^{2}$ & ${b}_{b}^{2}$ & ${a}_{a}^{2}$\\
\hline
 ${a}_{a}^{0}$ & ${b}_{a}^{1}$ & ${b}_{b}^{2}$ & ${a}_{b}^{2}$ & ${a}_{a}^{2}$\\
\hline
 ${b}_{b}^{0}$ & ${b}_{b}^{0}$ & ${a}_{b}^{1}$ & ${a}_{b}^{2}$ & ${b}_{a}^{2}$\\
\hline
 ${b}_{b}^{0}$ & ${b}_{b}^{0}$ & ${a}_{b}^{0}$ & ${a}_{b}^{1}$ & ${a}_{a}^{2}$\\
\hline
 ${a}_{a}^{0}$ & ${a}_{a}^{0}$ & ${a}_{a}^{0}$ & ${a}_{a}^{0}$ & ${b}_{a}^{1}$\\
\hline
\end{tabular}
\end{tabular}
\end{table}
\setlength{\tabcolsep}{6pt}

Informally, for any local column $col \in \Gamma^{m,1}$, and any column picture
$p \in \Sigma^{m,1}$, the local column $col' \in \Gamma^{m,1}$, is
univocally determined as follows. If $i$ is a position in $col$ so that
$col(i,1) = {x'}_{y'}^{1}$, $p(i+1,1) = x$ and $p(1,1) = y$ then $col'(i + 1, 1)
= x_{y}^{1}$. Above position $i + 1$ is $col'(j,1) = x_{y}^{2}$ iff $p(j,1) = x$
and $p(1,1) = y$. Below this diagonal position is $col'(j, 1) = x_{y}^{0}$ iff
$p(j,1) = x$ and $col(j, 1) = {x'}_{y}^{0}$.

We can see $T$ is $l2r$-unambiguous and hence $L_{fr=fc}\in$ Col-UREC.

\end{frame}

\begin{frame}
\frametitle{Closure properties and language hierarchy}

\begin{thm}
UREC $\subset$ REC ($L_{(l_2(p)) = (l_2(p) - 1)} \in REC$ but $L_{(l_2(p)) =
(l_2(p-1))} \not\in UREC)$\\
Col-UREC $\cup$ Row-UREC $\subseteq$ UREC.
\end{thm}

\begin{thm}
UREC is closed under projection, disjoint union, intersection and rotation, and it is
not closed under row and column concatenation and under row and column closures.
\end{thm}

\begin{thm}
It is decidable whether a tiling system is column- or row-unambiguous while it
is undecidable whether it is unambiguous.
\end{thm}
\end{frame}